package my.jwds.p398;

import java.util.*;

public class Pick {

    public static void main(String[] args) {

        Solution obj = new Solution(new int[]{1,2,2,3,3,3});
        long start = System.currentTimeMillis();
        System.out.println(obj.pick(1));
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    static class Solution {

        Map<Integer, List<Integer>> map = new HashMap<>();
        Random random = new Random();
        public Solution(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                List<Integer> list = map.get(nums[i]);
                if (list == null){
                    list = new ArrayList<>();
                    map.put(nums[i],list);
                }
                list.add(i);
            }
        }

        public int pick(int target) {
            List<Integer> list = map.get(target);
            return list.get((int) (random.nextDouble() * list.size()));
        }


    }

    static class Solution1 {

        int[] nums;
        Random random = new Random();
        public Solution1(int[] nums) {
            this.nums = nums;
        }

        public int pick(int target) {
            int count = 0;
            int res = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == target){
                    count++;
                    if (random.nextInt(count) == 0)res = i;
                }

            }
            return res;
        }


    }
}